package com.zds.leetcode;

import java.util.HashSet;
import java.util.Set;

public class q_128 {
    public static void main(String[] args) {
        q_128 q = new q_128();
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(q.longestConsecutive(nums));
    }

    public int longestConsecutive(int[] nums) {
        if(nums.length==0) return 0;
        // 利用哈希的结构降低复杂度
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        // 但这道题可能存在多个序列，所以需要遍历所有的起点
        int sum = 1;
        for (int num : set) {
            // 判断是不是起点
            // todo 判断是不是起点，和判断++是否存在，这其中的复杂度差异很大，这题真的玄学
            if (!set.contains(num - 1)) {
                int cursum = 1;
                while (set.contains(++num)) {
                    cursum++;
                }
                // 如果 cursum > sum 则更新 sum
                sum = Math.max(sum, cursum);
            }
        }

        return sum;
    }
}
